package jzOffer;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Num48 {
    //滑动窗口
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0) return 0;
        int i=0;
        int j=-1;
        char[] ch=s.toCharArray();
        Set<Character> set=new HashSet<>();
        int len=Integer.MIN_VALUE;
        while(j+1<ch.length){
            while(j+1<ch.length && !set.contains(ch[j+1])){
                set.add(ch[j+1]);
                j++;
            }
            len=Math.max(j-i+1,len);
            set.remove(ch[i]);
            i++;
        }
        return len;
    }
    //动归+哈希表
//    public int lengthOfLongestSubstring(String s) {
//        int n=s.length();
//        int tmp=0,res=0;
//        Map<Character,Integer> map=new HashMap<>();
//        for(int i=0;i<n;i++){
//            int j=map.getOrDefault(s.charAt(i),-1);
//            map.put(s.charAt(i),i);
//            tmp=tmp<i-j?tmp+1:i-j;
//            res=Math.max(tmp,res);
//        }
//        return res;
//    }
    //动归+线性查找（从后往前）
//    public int lengthOfLongestSubstring(String s) {
//        int n=s.length();
//        int tmp=0,res=0;
//        for(int i=0;i<n;i++){
//            int j=i-1;
//            while(j>=0 && s.charAt(j)!=s.charAt(i)) j--;
//            tmp=tmp<i-j?tmp+1:i-j;
//            res=Math.max(tmp,res);
//        }
//        return res;
//    }
}
